package com.test.daily.leetcode.y2022.m07.day0713.v02;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/7/13 下午 11:58
 * @version: 1.0
 */
public class Solution {
    public static class MyHeap {
        int limit;
        int heapSize;
        int[] heap;

        public MyHeap(int limit) {
            this.limit = limit;
            this.heapSize = 0;
            this.heap = new int[limit];
        }

        public void swap(int[] arr, int i, int j) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }

        public void heapfy(int[] arr, int index, int heapSize) {
            int left = index * 2 + 1;
            while (arr[left] < arr[index]) {
                int largest = left + 1 < heapSize && arr[left + 1] < arr[left] ? left + 1 : left;
                largest = arr[largest] < arr[index] ? index : largest;
                if (largest == index) {
                    break;
                }
                swap(arr, index, largest);
                index = largest;
                left = index * 2 + 1;
            }
        }

        public void heapInsert(int[] arr, int index) {
            while (arr[index] < arr[(index - 1) / 2]) {
                swap(arr, index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        public void push(int value) {
            if (heapSize == limit) {
                throw new RuntimeException("is full");
            }
            heap[heapSize] = value;
            heapInsert(heap, heapSize++);
        }

        public int pop() {
            int ans = heap[0];
            swap(heap, 0, --heapSize);
            heapfy(heap, 0, heapSize);
            return ans;
        }

        public void heapSort(int[] arr) {
            if (arr == null || arr.length < 2) {
                return;
            }
            int heapSize = arr.length;
            for (int i = arr.length; i >= 0; i--) {
                heapfy(arr, 0, --heapSize);
            }
            heapSize = arr.length;
            swap(arr, 0, --heapSize);
            while(heapSize >=0){
                heapfy(arr, 0,heapSize);
                swap(arr, 0, --heapSize);
            }
        }

    }
}
